package lc.q1_50;

import java.util.Arrays;
import java.util.Random;

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 *
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 *
 * 你的算法时间复杂度必须是 O(log n) 级别。
 *
 * 如果数组中不存在目标值，返回 [-1, -1]。
 *
 */
public class Q34 {

    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1,-1};
        }
        return searchRange(nums,0, nums.length, target);
    }

    private int[] searchRange(int[] nums, int start, int end, int target) {
        if (nums[start] > target || nums[end-1] < target) {
            return new int[]{-1,-1};
        }
        int mid = (start + end) / 2;
        if (nums[mid] > target) {
            // 往左边查
            return searchRange(nums, start, mid, target);
        } else if (nums[mid] < target) {
            // 往右边查
            return searchRange(nums, mid, end, target);
        } else {
            // 相等的情况如何处理
            // 在左边寻找最小位置，右边寻找最大位置
            // 不包含end
            int min = searchMin(nums, start, mid, target);
            int max = searchMax(nums, start, end, target);
            min = min == -1?mid:min;
            max = max == -1?mid:max;
            return new int[]{min, max};
        }
    }

    private int searchMin(int[] nums, int start,int end, int target) {
        // 注意target肯定不比任何的nums小
        if (target == nums[start]) {
            return start;
        }
        if (end - start <= 1) {
            return end;
        }
        int mid = (start + end) / 2;
        if (target == nums[mid]) {
            return searchMin(nums, start, mid, target);
        } else {
            return searchMin(nums, mid, end, target);
        }
    }

    private int searchMax(int[] nums, int start, int end, int target) {

        if (target == nums[end-1]) {
            return end - 1;
        }
        if (end - start <= 1) {
            return start;
        }
        int mid = (start + end) /2;
        if (nums[mid] > target) {
            return searchMax(nums, start, mid, target);
        } else {
            return searchMax(nums, mid, end, target);
        }

    }

    public static void main(String[] args) {
        // 创建一个数组
        Random random = new Random(System.currentTimeMillis());
        final int max = random.nextInt(30);
        int[] nums = new int[0];
        for (int i = 0; i < max+1; i++) {
            final int times = random.nextInt(10)+1;
            int length = nums.length;
            nums = Arrays.copyOf(nums, length + times);
            for (int j = 0; j < times; j++) {
                nums[length+j] = i;
            }
        }
        nums = new int[]{2,2};
        for (int num : nums) {
            System.out.print(num+"\t");
        }
        System.out.println();
        final Q34 q34 = new Q34();
        int target = random.nextInt(max);
        target = 2;
        System.out.println(target);
        final int[] ints = q34.searchRange(nums, target);
        for (int anInt : ints) {
            System.out.print(anInt + "\t");
        }
        System.out.println();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                System.out.print(i +"\t");
            }
        }
        System.out.println();
    }



}
